import collections
# 判断两个树是否相同
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 方法1：深度优先搜索。就是递归，比完根节点比较左子树，在比较右子树
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: # 这种方法简单，可以一直记住
    # 判断两个二叉树是否相同.这个递归可以。深度优先搜索
    if not p and not q:
        return True
    if not p or not q:
        return False
    elif p.val != q.val:  # 根节点相等，左节点是否相同
        return False
    else:
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

# 广度优先搜索。根本思路是建立一个队列，在处理父节点的时候将父节点的儿子加入队列
# 可以自己写队列数据结构，也可以利用别人已经写好的包，也可以就用列表来操作
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
    if not p and not q:
        return True
    if not p or not q:
        return False
    queue1 = collections.deque([p])
    queue2 = collections.deque([q])
    # 遍历完之后应该是两个队列都是空的
    while queue1 and queue2:
        node1 = queue1.popleft()
        node2 = queue2.popleft()    # 同时弹出一个相同位置的节点
        if node1.val != node2.val:
            return False
        # 接着将他们的左右子树(如果有的话加入队列)并判断结构是否相同
        left1, right1 = node1.left, node1.right
        left2, right2 = node2.left, node2.right
        # 简单易懂写就是是否都存在左右节点啥的
        if left1 ^ left2:   # 有一个为空不相等
            return False
        if right1 ^ right2: # 有一个为空，不相等
            return False
        if left1:
            queue1.append(left1)
        if left2:
            queue2.append(left2)
        if right1:
            queue1.append(right1)
        if right2:
            queue2.append(right2)
    return True